
// DFT实现
var PI = 3.14159

//复数乘法
//z1 = a1 + jb1，用[a1, b1]表示z1
//z2 = a2 + jb2，用[a2, b2]表示z2
function complexMul(z1, z2) {
    return [z1[0] * z2[0] - z1[1] * z2[1], z1[0] * z2[1] + z2[0] * z1[1]];
}


// 复数加法
function complexAdd(z1, z2) {
    return [z1[0] + z2[0], z1[1] + z2[1]];
}

// 复指数转复数，z=r*(e^jθ)=r*cos(θ)+r*jsin(θ) 其中θ为复数
function r_exp(r, theta) {
    return [r * Math.cos(theta), r * Math.sin(theta)];
}

// 对xn求N点DFT[x(n)]，x(n)为复数，即x(0)=a0+jb0, x(1)= a1+jb1...可以标识为x[0]=[a0, b0]...x[n]=[an, bn]
// 所以参数xn=[[a0, b0], [a1, b1],..., [an, bn]]
// DFT点数N就是圆的个数, len_xn为xn长度
function DFT(xn, N, len_xn){
    var Xk=[];
    for(k=0; k<N; k++){
        Xk[k] = [0, 0];
        for(var n=0; n<len_xn; n++){
            var W_Nkn = r_exp(1, -2*PI*k*n / N)   // W因子
            Xk[k] = complexAdd(Xk[k], complexMul(xn[n], W_Nkn))
        }
    }
    return Xk;
}

// 获取半径
function get_Rk(xn, N, len_xn){
    Xk = DFT(xn, N, len_xn);
    for(var k=0; k<N; k++){
        Xk[k][0]/=N;
        Xk[k][1]/=N;
    }
    return Xk;
}

// 由Xk获取xn，由于n是与时间有关，所以每隔一定时间(时间是自己增加的)计算x[0]、x[1]...即可，无需一次性求出x[0]...x[n]
//N与DFT的N一样，len_xn是xn的长度
function IDFT(Xk, N){
    xn = []
    // for (var n = 0; n<len_xn; n++) {
    //     xn[n]=[0, 0];
    for(var k=0; k<N; k++){
        var W_Nkn = r_exp(1, 2 * PI * k * time_n / N)   // W-因子
        xn[time_n] = complexAdd(xn[time_n], complexMul(Xk[k], W_Nkn));
    }
    return xn;
}

function get_xn_from_pathArr(pathArr){
    xn=[]
    for (var i = 0; i < pathArr.length / 2; i++) {
        xn[i] = [pathArr[2 * i] - pathArr[0], pathArr[2 * i + 1] - pathArr[1]]; //注意path是二维数组
    }
    return xn;
}